// 定义二叉树节点
case class TreeNode(value: Int, left: Option[TreeNode] = None, right: Option[TreeNode] = None)

object BinaryTreePrinter {
  // 前序遍历打印 (根 -> 左 -> 右)
  def preOrderTraversal(root: Option[TreeNode]): Unit = {
    root.foreach { node =>
      print(s"${node.value} ")
      preOrderTraversal(node.left)
      preOrderTraversal(node.right)
    }
  }

  // 中序遍历打印 (左 -> 根 -> 右)
  def inOrderTraversal(root: Option[TreeNode]): Unit = {
    root.foreach { node =>
      inOrderTraversal(node.left)
      print(s"${node.value} ")
      inOrderTraversal(node.right)
    }
  }

  // 后序遍历打印 (左 -> 右 -> 根)
  def postOrderTraversal(root: Option[TreeNode]): Unit = {
    root.foreach { node =>
      postOrderTraversal(node.left)
      postOrderTraversal(node.right)
      print(s"${node.value} ")
    }
  }

  // 层序遍历打印 (广度优先搜索)
  def levelOrderTraversal(root: Option[TreeNode]): Unit = {
    import scala.collection.mutable.Queue

    val queue = Queue[TreeNode]()
    root.foreach(queue.enqueue)

    while (queue.nonEmpty) {
      val node = queue.dequeue()
      print(s"${node.value} ")

      node.left.foreach(queue.enqueue)
      node.right.foreach(queue.enqueue)
    }
  }

  def main(args: Array[String]): Unit = {
    // 构建一个示例二叉树
    val tree = TreeNode(
      1,
      Some(TreeNode(
        2,
        Some(TreeNode(4)),
        Some(TreeNode(5))
      )),
      Some(TreeNode(3))
    )

    println("前序遍历:")
    preOrderTraversal(Some(tree))  // 输出: 1 2 4 5 3
    println("\n中序遍历:")
    inOrderTraversal(Some(tree))   // 输出: 4 2 5 1 3
    println("\n后序遍历:")
    postOrderTraversal(Some(tree)) // 输出: 4 5 2 3 1
    println("\n层序遍历:")
    levelOrderTraversal(Some(tree)) // 输出: 1 2 3 4 5
  }
}